package 我的Java学习_算法基础.day_05;

import java.util.Arrays;

public class _085_字符串匹配之后缀数组_中 {
    /***
     * logN*NlogN
     * @param src
     * @return
     */
    public static Suff[] getSa2(String src) {
        int strLength = src.length();
        //rank是下标到排名的映射
        int[] rk = new int[strLength];//suffix array
        Suff[] suffixArray = new Suff[strLength];
        for (int k = 1; k <= strLength; k *= 2) {//logN趟
            for (int i = 0; i < strLength; i++) {//k代表截取范围，一开始只截一个字符，即每个字符参与排序，下次两个字符参与排序
                String suffI = src.substring(i, i + k > strLength ? strLength : i + k);//增量，此处可能越界
                suffixArray[i] = new Suff(suffI, i);
            }
            if (k == 1) {//一个字符
                Arrays.sort(suffixArray);//NlogN
            } else {
                //填充完成，开始排序NlogN
                final int kk = k;
                Arrays.sort(suffixArray, (o1, o2) -> {
                    //不是基于字符串比较，而是利用之前的rank
                    int i = o1.index;
                    int j = o2.index;
                    if (rk[i] == rk[j]) {
                        try {
                            return rk[i + kk / 2] - rk[j + kk / 2];
                        } catch (ArrayIndexOutOfBoundsException e) {
                            return o1.str.length() - o2.str.length();
                        }
                    } else {
                        return rk[i] - rk[j];
                    }
                });
            }
            //排序完成后生成rank，即给定下标，给出排名
            int r = 0;
            rk[suffixArray[0].index] = r;
            for (int i = 1; i < strLength; i++) {
                if (suffixArray[i].compareTo(suffixArray[i - 1]) == 0) {
                    rk[suffixArray[i].index] = r;
                } else {
                    rk[suffixArray[i].index] = ++r;
                }
            }
        }
        return suffixArray;
    }
}
